package com.leetcode.partition5;

/**
 * @author `RKC`
 * @date 2021/10/10 9:20
 */
public class LC441排列硬币 {

    public static int arrangeCoins(int n) {
        //等差数列求和公式，a1为1，公差为1 s(n) = n(n + 1) / 2，而题目的最后一层可能是满的可能没有满
        //设有c个硬币，满足 s(n) < c，求根公式：ans = (sqrt(8c + 1) - 1) / 2
        double numerator = Math.sqrt(8L * n + 1) - 1;
        return (int) (numerator / 2);
    }

    public static void main(String[] args) {
//        System.out.println(arrangeCoins(2));
        System.out.println(arrangeCoins(10));
//        System.out.println(arrangeCoins(3));
//        System.out.println(arrangeCoins(5));
//        System.out.println(arrangeCoins(6));
//        System.out.println(arrangeCoins(8));
    }
}
